package com.arron.algorithm.leetcodetop100.技巧.摩尔投票;


import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * Leetcode 169. 多数元素
 *  摩尔投票，相互抵消
 *      https://leetcode.cn/problems/majority-element-ii/solutions/1/liang-fu-dong-hua-yan-shi-mo-er-tou-piao-fa-zui-zh/
 */
public class 多数元素 {


    public static void main(String[] args) {
        int a[] = {2,2,1,1,1,2,2};
        System.out.println(majorityElement3(a));
    }

    /**
     * 空间复杂度O(n/2) =O(n) 时间复杂度：O(n)
     * 使用hashmap +存储
     * @param nums
     * @return
     */
    public static int majorityElement(int[] nums) {


        Map<Integer,Integer> map = new HashMap<>();
        int maxTimes =0;
        int maxNum =0;

        for (int i = 0; i < nums.length; i++) {
            if(map.get(nums[i]) == null){
                map.put(nums[i],1);
            }else {
                Integer integer = map.get(nums[i]);
                map.put(nums[i],++integer);
            }
        }
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (entry.getValue()>maxTimes){
                maxTimes = entry.getValue();
                maxNum = entry.getKey();
            }

        }
        return maxNum;
    }


    /**
     * 利用众数原理，排序后，出现次数最多的元素必在中间
     * @param nums
     * @return
     */
    public static int majorityElement2(int[] nums) {

        Arrays.sort(nums);

        return nums[nums.length/2];
    }


    /**
     * 利用消除法 ： 两个元素相同则count++，不相等则count--，如果count==0，则将winner复制给下一个元素
     * 时间复杂度：O(n)
     * 空间复杂读 ： O(1)
     * @param nums
     * @return
     */
    public static int majorityElement3(int[] nums) {

        int cd = nums[0];

        int count =0;
        for(int i=0;i<nums.length;i++){
            if(nums[i] == cd){
                count++;
                continue;
            }


            if(count ==0){
                cd = nums[i];
                count++;
                continue;
            }
            count--;
        }

        return cd;

    }









}
